/**
 * 项目名称: 二叉排序树.cpp
 * 项目路径: study/DataStructure/数据结构/查找/树形查找
 * 编辑时间: 2024年08月20日09时35分18秒
 * 用   户: 轻尘
 */

#include <bits/stdc++.h>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

//二叉排序树结点
struct BSTNode{
    int key;
    struct BSTNode *lchild,*rchild;
};

/**
 * 二叉排序树中查找值为key的结点
 * @param T
 * @param key
 * @return
 */
BSTNode *BST_Search(BSTNode *T,int key){
    while (T!= nullptr && key != T->key)//若树为空或等于跟结点值,则结束循环
        if(key<T->key)T=T->lchild;//小于,则在左子树查找
        else T=T->rchild;//大于,则在右子树查找
    return T;
}

/**
 * 前序序列构造二叉排序树
 * @param data
 * @param u
 * @param minv
 * @param maxv
 * @return
 */
TreeNode* insert(vector<int>& data,int & u,int minv,int maxv){
    if(u == data.size() || data[u]<minv || data[u] > maxv)return nullptr;
    auto root = new TreeNode(data[u++]);
    root->left = insert(data,u, minv,root->val);
    root->right = insert(data,u,root->val+1,maxv);
    return root;
}

/**
 * 二叉排序树插入关键字为k的新节点(递归实现)
 * @param T
 * @param k
 * @return
 */
int BST_Insert(BSTNode *&T,int k){
    if(T== nullptr){//原数为空,新插入的结点为根节点
        T=new BSTNode;
        T->key = k;
        T->lchild = T->rchild = nullptr;
        return 1;//返回1,插入成功
    }
    else if(k==T->key)return 0;//树中存在相同关键字的结点,插入失败
    else if(k<T->key)return BST_Insert(T->lchild,k);//插入到左子树
    else return BST_Insert(T->rchild,k);//插入到右子树
}

/**
 * 按照给定二叉排序树str[]中的关键字序列建立二叉排序树
 * @param T
 * @param str
 * @param n
 */
void Creat_BST(BSTNode *&T,int str[],int n){
    T= nullptr;//初始时T为空树
    int i =0;
    while (i<n){//依次将每个关键字插入到二叉排序树中
        BST_Insert(T,str[i]);
        i++;
    }
}
